#include "HiranipraShared.h"

#include "Collections/LFFreeList.h"

#ifndef _SHARED_COLLECTIONS_LFQUEUE_H_
#define _SHARED_COLLECTIONS_LFQUEUE_H_

namespace Hiranipra {

	// http://www.boyet.com/Articles/LockfreeQueue.html

	template<class T>
	class LFQueue
	{
	public:
		LFQueue( uint32 capacity = 0, bool waitOnDequeue = false ) :
			_capacity( capacity ), _waitOnDequeue( waitOnDequeue ),
			_freeList( capacity )
		{
			_head = _freeList.AllocateNode();
			_tail = _head;
		}

		~LFQueue()
		{
			delete _head;
			_head = NULL;
			_tail = NULL;
		}

		bool Enqueue( T value )
		{
			volatile LinkNode<T>* oldTail = NULL;
			volatile LinkNode<T>* oldTailNext = NULL;

			LinkNode<T>* node = _freeList.AllocateNode();
			node->Value = value;

			// loop until we have managed to update the tail's Next link 
			// to point to our new node
			bool updatedNewLink = false;
			do
			{
				// make local copies of the tail and its Next link, but in 
				// getting the latter use the local copy of the tail since
				// another thread may have changed the value of tail
				oldTail = _tail;         
				oldTailNext = oldTail->Next; 

				// providing that the tail field has not changed...
				if( _tail == oldTail )
				{
					// ...and its Next field is null
					if( oldTailNext == NULL )
					{
						// ...try to update the tail's Next field
						updatedNewLink = CAS( &_tail->Next, NULL, node );
					}

					// if the tail's Next field was non-null, another thread
					// is in the middle of enqueuing a new node, so try and 
					// advance the tail to point to its Next node
					else
					{
						CAS( &_tail, oldTail, oldTailNext );
					}
				}
			} while( updatedNewLink == false );

			// try and update the tail field to point to our node; don't
			// worry if we can't, another thread will update it for us on
			// the next call to Enqueue()
			CAS( &_tail, oldTail, node );
			_count++;

			return true;
		}

		bool Dequeue( T& value )
		{
			T result = NULL;
			volatile LinkNode<T>* oldHead = _head;

			// loop until we manage to advance the head, removing 
			// a node (if there are no nodes to dequeue, we'll exit
			// the method instead)
			bool haveAdvancedHead = false;
			do
			{
				// make local copies of the head, the tail, and the head's Next 
				// reference
				oldHead = _head;
				volatile LinkNode<T>* oldTail = _tail;
				volatile LinkNode<T>* oldHeadNext = oldHead->Next;

				// providing that the head field has not changed...
				if( oldHead == _head )
				{
					// ...and it is equal to the tail field
					if( oldHead == oldTail )
					{
						// ...and the head's Next field is null
						if( oldHeadNext == NULL )
						{
							// ...then there is nothing to dequeue
							if( _waitOnDequeue == true )
							{
								Thread::yield();
								continue;
							}
							else
								return false;
						}

						// if the head's Next field is non-null and head was equal to the tail
						// then we have a lagging tail: try and update it
						CAS( &_tail, oldTail, oldHeadNext );
					}

					// otherwise the head and tail fields are different
					else
					{
						// grab the item to dequeue, and then try to advance the head reference
						value = oldHeadNext->Value;
						haveAdvancedHead = CAS( &_head, oldHead, oldHeadNext );
					}
				}
			} while( haveAdvancedHead == false );
			_freeList.ReleaseNode( ( LinkNode<T>* )oldHead );
			_count--;
			return true;
		}

	private:
		uint32		_capacity;
		bool		_waitOnDequeue;
		uint32		_count;
		
		LFFreeList<T>			_freeList;

		volatile LinkNode<T>*	_head;
		volatile LinkNode<T>*	_tail;
	};

}

#endif // _SHARED_COLLECTIONS_LFQUEUE_H_
